﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using alib.Debugging;

using alib.Hashing;
using alib.Enumerable;
using alib.Collections;
using alib.Array;
using alib.String;

namespace alib.dg
{
#if DEBUG
	using String = System.String;
	using Enumerable = System.Linq.Enumerable;
	using Array = System.Array;
	using BitArray = System.Collections.BitArray;
	using debug;

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// 
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public partial class rw_string_graph : rw_data_graph<String, String>, IStringGraph
	{
		[DebuggerStepThrough]
		public static bool moniker(Vref vr, out String s)
		{
			if (vr == Vref.NotValid)
				s = "NotValid";
			else if (vr == (int)status.NotInFreelist)
				s = "NotInFreelist";
			else if (vr < 0)
				s = "(vref < 0)";
			else
			{
				s = "V" + ((int)vr);
				return false;
			}
			return true;
		}
		[DebuggerStepThrough]
		public static bool moniker(Eref er, out String s)
		{
			status es = (status)er;
			if (es == status.NotValid)
				s = "NotValid";
			else if (es == status.fe_BlockSingleton)
				s = "sing";
			else if (es == status.fe_BlockStart)
				s = "start";
			else if (es == status.fe_BlockEnd)
				s = "end";
			else if (er == Eref.None)
				s = "Eref.None";
			else if (er < 0)
				s = "(eref < 0)";
			else
			{
				//var g = dg._singleton;
				//s = String.Format("Eref error: v_from:{0} v_to:{1} e_next:{2} value{3}",
				//	(int)g.E[er].e_next,
				//	(int)g.E[er].v_from,
				//	(int)g.E[er].v_to,
				//	(int)g.E[er].value);

				s = "E" + ((int)er);
				return false;
			}
			return true;
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		eent_dbg[] edbg;
		//[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		[DebuggerDisplay("Count: {EdgeCount}/{EdgeAlloc} free: {c_edge_free}", Name = "=== EDGES")]
		public eent_dbg[] z01_EDGES
		{
			[DebuggerStepThrough]
			get
			{
				int c = EdgeAlloc;
				if (edbg == null || edbg.Length != c)
				{
					edbg = new eent_dbg[c];
					for (Eref i = Eref.Zero; i < c; i++)
						edbg[i] = new eent_dbg(this, i);
				}
				return edbg;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		vent_dbg[] vdbg;
		//[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		[DebuggerDisplay("Count: {VertexCount}/{VertexAlloc} free: {c_vertex_free}", Name = "=== VERTICIES")]
		public vent_dbg[] z02_VERTICIES
		{
			[DebuggerStepThrough]
			get
			{
				int c = VertexAlloc;
				if (vdbg == null || vdbg.Length != c)
				{
					vdbg = new vent_dbg[c];
					for (Vref i = Vref.Zero; i < c; i++)
						vdbg[i] = new vent_dbg(this, i);
				}
				return vdbg;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		debug_freelist_entry[] fldbg;
		[DebuggerDisplay("", Name = "=== EDGE FREELISTS")]
		public debug_freelist_entry[] z03_FREELISTS
		{
			[DebuggerStepThrough]
			get
			{
				if (fldbg == null)
				{
					fldbg = new debug_freelist_entry[EdgeFreelistCount];
					for (int i = 0; i < EdgeFreelistCount; i++)
						fldbg[i] = new debug_freelist_entry(this, i);
				}
				return fldbg;
			}
		}
	};

	[DebuggerDisplay("{ToString(),nq}")]
	public class debug_freelist_entry
	{
		public debug_freelist_entry(rw_string_graph g, int block_size)
		{
			this.g = g;
			this.block_size = block_size;
		}
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		readonly rw_string_graph g;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		readonly int block_size;

		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public eent_dbg[] _entries
		{
			get
			{
				var arr = g.freelist_entries(block_size).ToArray();
				eent_dbg[] ret = new eent_dbg[arr.Length];
				for (int i = 0; i < arr.Length; i++)
					ret[i] = new eent_dbg(g, arr[i], 0);
				return ret;
			}
		}

		public override String ToString()
		{
			int c = g.freelist_entries(block_size)._Count();
			return c == 0 ? "" : c.ToString();
		}
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// 
	public partial class rw_graph : dg
	{
		[DebuggerStepThrough]
		/// <summary> works with free list entries only </summary>
		int _discover_self_ix_via_freelist(int prv)
		{
			int nxt = -1;
			if (prv < 0 && ~prv < edge_freelists.Length)
				nxt = edge_freelists[~prv];
			else if (prv >= 0 && prv < EdgeAlloc)
				nxt = E[prv].nxt;
			return nxt >= 0 && nxt < EdgeAlloc && E[nxt].IsFree && E[nxt].prv == prv ?
				nxt : (int)status.NotValid;
		}

		int check_vertex_freelist()
		{
			int ix = vertex_freelist, c = 0;
			while (ix != (int)status.FreelistTerm)
			{
				ix = ((int_λVertex)((ref Vertex x) =>
				{
					if (x.status != status.free || x.prv != (int)status.NotValid || x.value != 0)
						throw new Exception();
					return x.nxt;
				}))(ref V[ix]);
				if (c++ > c_vertex_free)
					throw new Exception();
			}
			return c;
		}

		int check_edge_freelist(out int c_blks)
		{
			int tot = 0;
			c_blks = 0;
			for (int block_size = 0; block_size < edge_freelists.Length; block_size++)
			{
				int _tmp;
				tot += check_edge_freelist(block_size, out _tmp);
				c_blks += _tmp;
			}
			return tot;
		}
		int check_edge_freelist(int list_num, out int c_blks)
		{
			int i = edge_freelists[list_num], c_rows = 0;
			c_blks = 0;
			while (i != (int)status.FreelistTerm)
			{
				int cblk = E[i].block_size;

				if (list_num > 0 && cblk != list_num)
					throw new Exception();

				if (cblk <= 0)
					throw new Exception();
				else if (cblk == 1)
				{
					if (E[i].status != status.fe_BlockSingleton)
						throw new Exception();
				}
				else
				{
					int i_end = get_block_end(i);
					for (int j = i; j <= i_end; j++)
					{
						if (j == i)
						{
							if (E[j].status != status.fe_BlockStart)
								throw new Exception();
							if (E[j].block_size != cblk)
								throw new Exception();
							if (E[j].prv == (int)status.NotInFreelist)
								throw new Exception();
							if (E[j].nxt == (int)status.NotInFreelist)
								throw new Exception();
						}
						else
						{
							if (j == i_end)
							{
								if (E[j].status != status.fe_BlockEnd)
									throw new Exception();
								if (E[j].block_size != cblk)
									throw new Exception();
							}
							else
							{
								if (E[j].status != status.free)
									throw new Exception();
								if (E[j].block_size != 0)
									throw new Exception();
							}

							if (E[j].prv != (int)status.NotInFreelist)
								throw new Exception();
							if (E[j].nxt != (int)status.NotInFreelist)
								throw new Exception();
						}
					}
				}

				c_rows += cblk;
				i = E[i].nxt;
				c_blks++;
			}
			return c_rows;
		}

		public IEnumerable<Eref> freelist_entries(int block_size)
		{
			int i = edge_freelists[block_size];
			while (i != (int)status.FreelistTerm)
			{
				yield return new Eref(i);
				i = E[i].nxt;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		public void check()
		{
			try
			{
				if (VertexAlloc - c_vertex_free != VertexCount)
					throw new Exception("AA");
				if (c_vertex_free != check_vertex_freelist())
					throw new Exception("CC");

				if (EdgeAlloc - c_edge_free != EdgeCount)
					throw new Exception("BB");
				int c_blks;
				if (c_edge_free != check_edge_freelist(out c_blks))
					throw new Exception("DD");
				if (c_blocks_free != c_blks)
					throw new Exception("EE");

				new check_helper(this);
				for (Eref i = Eref.Zero; i < EdgeAlloc; i++)
				{
					var eed = new debug.eent_dbg((rw_string_graph)this, i);
#if false
					var _x5 = eed.ProxyOk;
					var _x1 = eed._e_next;
					var _x2 = eed._v_from;
					var _x3 = eed._v_to;
					var _x4 = eed._value;
					var _x6 = eed.z10_coref;
					var _x7 = eed.z20_parent;
					var _x10 = eed.ToString();
#endif
				}
				for (Vref i = Vref.Zero; i < VertexAlloc; i++)
				{
					var vvd = new debug.vent_dbg((rw_string_graph)this, i);
#if false
					var _x1 = vvd.ProxyOk;
					var _x2 = vvd._e_in;
					var _x3 = vvd._e_out;
					var _x4 = vvd._c_out;
					var _x5 = vvd._value;
					var _x6 = vvd.z10_up;
					var _x7 = vvd.z11_down;
					var _x8 = vvd.z30_paths;
					var _x9 = vvd.get_below();
					var _x13 = vvd.ToString();
#endif
				}
			}
			catch (Exception ex)
			{
				Debug.Print(ex.StackTrace.ToString());
			}
		}
	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// 
	public struct check_helper
	{
		public check_helper(dg graph)
		{
			this.graph = graph;
			this.peer_edge_count = 0;
			this.v_in_counts = new int[graph.V.Length];

			if (graph is rw_graph)
				check_rw((rw_graph)graph);
			else
				check_ro();

			int ccc = v_in_counts.Sum();

			if (peer_edge_count != graph.EdgeCount)
				throw new Exception(String.Format("peer list error: {0} (expecting {1})", peer_edge_count, graph.EdgeCount));

			//Debug.Print("Peer count: {0}  EdgeCount: {1}", peer_edge_count, rwg.EdgeCount);

			//Debug.Print("{0}-{1:X8}  e:{2}  v:{3} check ok", graph.GetType().Name, graph.GetHashCode(), graph.EdgeCount, graph.VertexCount);
		}

		readonly dg graph;
		dg.Edge[] E { get { return graph.E; } }
		dg.Vertex[] V { get { return graph.V; } }
		int[] v_in_counts;
		int peer_edge_count;

		void check_ro()
		{
			_check_verticies();

			_check_edges();
		}

		void check_rw(rw_graph graph)
		{
			int ckv, cke;
			if ((ckv = _check_rw_verticies(graph)) != graph.c_vertex_free)
				throw new Exception();

			if ((cke = _check_rw_edges(graph)) != graph.c_edge_free)
				throw new Exception();
		}

		void _check_verticies()
		{
			int _cva = graph.VertexAlloc;
			for (Vref vr = new Vref(0); vr < _cva; vr++)
				check_vertex(vr, ref V[vr]);
		}

		int _check_rw_verticies(rw_graph graph)
		{
			int _cva = graph.VertexAlloc, fv = 0;
			bool b;
			for (Vref vr = new Vref(0); vr < _cva; vr++)
			{
				if ((b = graph._vertex_freelist_contains(vr)) != V[vr].IsFree)
					throw new Exception("vertex free state is inconsitent");
				else if (!b)
					check_vertex(vr, ref V[vr]);
				else
					fv++;
			}
			return fv;
		}

		void _check_edges()
		{
			int _cea = graph.EdgeAlloc;
			for (Eref er = Eref.Zero; er < _cea; er++)
				check_edge(er, ref E[er]);
		}

		int _check_rw_edges(rw_graph graph)
		{
			int _cea = graph.EdgeAlloc, fe = 0;
			for (Eref er = Eref.Zero; er < _cea; er++)
			{
				if (E[er].IsFree)
				{
					if (E[er].HasSize)
					{
						int q = graph._find_edge_freelist(er);
						if (q == -1)
							throw new Exception("edge free state is inconsitent");
					}
					fe++;
				}
				else
					check_edge(er, ref E[er]);
			}
			return fe;
		}

		void check_vertex(Vref vr, ref dg.Vertex v)
		{
			if (v.e_in == Eref.None)
			{
				/// top o.k.
			}
			else if (!graph.edge_is_valid(v.e_in))
				throw new Exception("in-edge must be valid and not free");
			else
			{
				if (graph.edge_target(v.e_in) != vr)
					throw new Exception("in-edge must target this vertex");
				/// ...
			}

			if (v.c_out < 0)
				throw new Exception("out-edge count cannot be negative");
			else if (v.c_out > 0)
			{
				if (v.e_out < 0)
					throw new Exception("out-edge pointer must be non-negative");

				var er_last = v.e_out + v.c_out;
				for (var er = v.e_out; er < er_last; er++)
				{
					if (E[er].IsFree)
						throw new Exception("out-edge is free");
					if (E[er].v_from != vr)
						throw new Exception("out-edge v_from does not refer to parent vertex");
					if (!graph.edge_is_valid(E[er].e_next))
						throw new Exception();
				}
			}
			else if (v.e_out != Eref.NotValid)
				throw new Exception("out-edge pointer must be Eref.NotValid if there are no out-edges");
		}

		void check_edge(Eref er, ref dg.Edge e)
		{
			if (e.IsFree)
				throw new Exception("appears free but not marked in freelist");

			if (!graph.vertex_is_valid(e.v_from))
				throw new Exception("'from' vertex must be valid and not free");

			if (!graph.vertex_is_valid(e.v_to))
				throw new Exception("'to' vertex must be valid and not free");

			check_edge_target(er, ref e);
		}

		void check_edge_target(Eref er, ref dg.Edge e)
		{
			Vref v_target = e.v_to;

			if (e.v_from == v_target)
				throw new Exception("edge cannot connect to itself");

			if (V[v_target].IsTop)
				throw new Exception("edge cannot target a 'top' vertex");

			bool s1 = er == V[v_target].e_in;
			bool s2 = graph.edge_is_master(er);
			if (s1 != s2)
				throw new Exception("inconsistent edge master status");

			int c = check_edge_next(er);

			if (s2)
				peer_edge_count += c;

			v_in_counts[v_target]++;
		}

		int check_edge_next(Eref er)
		{
			Eref e_cur = E[er].e_next;

			if (!graph.edge_is_valid(e_cur))
				throw new Exception("'e_next' must be valid ");

			Vref v_target = E[er].v_to;

			int c = 1;
			while (e_cur != er)
			{
				if (e_cur == Eref.NotValid)
					throw new Exception("invalid edge in peer list");

				if (e_cur < 0)
					throw new Exception("unknown edge in peer list");

				if (E[e_cur].v_to != v_target)
					throw new Exception("peer edges don't point to same target");

				e_cur = E[e_cur].e_next;
				if (++c > 200)
					throw new Exception("probable cycle in peer list");
			}

			if (c > 1 && !graph.edge_target_coreferenced(er))
				throw new Exception("wrong coref status");

			if (c != graph.vertex_in_edges(v_target).Length)
				throw new Exception("incorrect master in-edge count");

			return c;
		}
	};
#endif
}
